package com.example

import java.io.{DataInputStream, FileInputStream}
import scala.annotation.tailrec

object QTreeFromGrid {
  // 从二进制文件中读取地图
  private def readMapBinary(path: String): Array[Array[CellState]] = {
    val size = 512
    val dis = new DataInputStream(new FileInputStream(path))
    val gridR = Array.ofDim[CellState](size, size)
    try {
      // 文件是紧凑存储的二进制格式
      val buffer = Array.ofDim[Byte](size * size)
      dis.readFully(buffer)
      for (i <- 0 until size; j <- 0 until size) {
        // 重要！注意这里，因为原始数据的xy坐标搞反了，这里做一下修正
        gridR(j)(i) = if (buffer(i * size + j) == 1) Empty else Obstacle
      }
    } finally {
      dis.close()
    }
    gridR
  }

  // 检查区域是否同质（全部空白或全部障碍物）
  private def isUniform(grid: Array[Array[CellState]], x: Int, y: Int, size: Int): Boolean = {
    val first = grid(x)(y)
    for {
      i <- x until x + size
      j <- y until y + size
    } {
      if (grid(i)(j) != first) return false
    }
    true
  }

  // 递归构建四叉树
  private def buildQuadTree(grid: Array[Array[CellState]], x: Int, y: Int, size: Int): QuadTree = {
    if (isUniform(grid, x, y, size)) {
      Leaf(grid(x)(y), Bounds(y, x, size))
    } else {
      val half = size / 2
      new Node(
        nw = buildQuadTree(grid, x, y, half),
        ne = buildQuadTree(grid, x, y + half, half),
        sw = buildQuadTree(grid, x + half, y, half),
        se = buildQuadTree(grid, x + half, y + half, half),
        bound = Bounds(y, x, size)
      )
    }
  }

  // 辅助方法：找到某个位置所属的分区大小
  @tailrec
  private def findBlockSize(tree: QuadTree, x: Int, y: Int, size: Int): Int = {
    tree match {
      case Leaf(_, _) => size
      case n: Node =>
        val half = size / 2
        if (x < half && y < half) findBlockSize(n.nw, x, y, half)
        else if (x < half && y >= half) findBlockSize(n.ne, x, y - half, half)
        else if (x >= half && y < half) findBlockSize(n.sw, x - half, y, half)
        else findBlockSize(n.se, x - half, y - half, half)
    }
  }

  // 为整个四叉树计算所有节点的邻居
  def computeAllNeighbors(root: QuadTree): Unit = {
    def traverse(node: QuadTree): Unit = {
      node match {
        case n: Node =>
          traverse(n.nw)
          traverse(n.ne)
          traverse(n.sw)
          traverse(n.se)
        case n: Leaf =>
          n.findNeighbors(root)
      }
    }
    traverse(root)
  }

  // 主程序
  def main(args: Array[String]): Unit = {
    println("You are now in QTreeFromGrid.main")
    println("We are going to test:")
    println("- load 512x512 map data from grids.data")
    println("- build QTree from grid data loaded")
    println("- compute all leaf neighbors in this QTree")
    println("- serialize QTree to the file serializeBinary.data")
    println("- test AStar path routing.")
    println("- visualize QTree struct, neighborhoods, path finding in grids.png")

    val mapSize = 512
    // load 512x512 map data from grids.data
    val grid = readMapBinary("D:\\temp\\jl\\grids.data")

    // build QTree from grid data loaded
    val quadTree = buildQuadTree(grid, 0, 0, mapSize)

    // compute all leaf neighbors in this QTree
    computeAllNeighbors(quadTree)

    // serialize QTree to the file serializeBinary.data
    QTreeSerializer.serializeCustom(quadTree, "D:\\temp\\jl\\serializeBinary.data")

    // test AStar path routing.
    val route = AStar.findPath(quadTree, 110, 338, 484, 372)
    println(route)

    // visualize QTree struct, neighborhoods, path finding in grids.png
    QTreeRender.renderQuadtree(quadTree, 512, "D:\\temp\\jl\\grids.png", route match {
      case Some(value) => value
      case _ => List[(Int, Int)]()
    })
  }
}
